|
In graph theory, the Lovász conjecture (1970) is a classical problem on Hamiltonian paths in graphs. It says: : Every finite connected vertex-transitive graph contains a Hamiltonian path. The original article of Lovász stated the result in the opposite, but this version became standard. In 1996 Babai published a conjecture sharply contradicting this conjecture,〔L. Babai, (Automorphism groups, isomorphism, reconstruction ), in ''Handbook of Combinatorics'', Vol. 2, Elsevier, 1996, 1447-1540.〕 but both conjectures remain widely open. It is not even known if a single counterexample would necessarily lead to a series of counterexamples. == Historical remarks == The problem of finding Hamiltonian paths in highly symmetric graphs is quite old. As Knuth describes it in volume 4 of ''The Art of Computer Programming'',〔D. E. Knuth, The Art of Computer Programming, Vol. 4, draft of section 7.2.1.2.〕 the problem originated in British campanology (bell-ringing). Such Hamiltonian paths and cycles are also closely connected to Gray codes. In each case the constructions are explicit. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Lovász conjecture」の詳細全文を読む スポンサード リンク
|